package com.javabasic.algorithm.leetcode;

import java.util.Arrays;

/**
 * @author xiongmin
 * @version 0.0.1
 * @description Created by work on 2021/10/6 11:54 下午
 * @see
 */
public class ThirdMaximumNumber {

    /**
     * 暴力解法：
     * 1. 先将数组排序
     * 2. 再遍历数组球第3大的数
     * @param nums
     * @return
     */
    public int thirdMax(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);

        if (len < 3) {
            return nums[len-1];
        } else {
            int tag = 0;
            for (int i = len-2; i >= 0; i--) {
                if (nums[i] != nums[i+1]) {
                    tag++;
                    if (tag == 2) {
                        return nums[i];
                    }
                }

            }
            return nums[len-1];
        }
    }

    /**
     * 解法二：O(n)时间复杂度
     * 一遍遍历即可求出结果
     * 思路：遍历一遍求出第一大、第二大、第三大的数
     * @param nums
     * @return
     */
    public int thirdMax2(int[] nums) {
        int len = nums.length;
        int first = Integer.MIN_VALUE, second = Integer.MIN_VALUE, third = Integer.MIN_VALUE;
        int firstChange = 0, secondChange = 0, thirdChange = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] >= first) {
                if (nums[i] == first) {
                    firstChange = firstChange == 0 ? ++firstChange : firstChange;
                    continue;
                }
                third = second;
                second = first;
                first = nums[i];
                if (firstChange >= 2) {
                    firstChange++;
                    secondChange++;
                    thirdChange++;
                } else if (firstChange == 1) {
                    firstChange++;
                    secondChange++;
                    if (secondChange > 1) {
                        thirdChange++;
                    }
                } else if (firstChange == 0) {
                    firstChange++;
                }

            } else if (nums[i] >= second) {
                if (nums[i] == second) {
                    secondChange = secondChange == 0 ? ++secondChange : secondChange;
                    continue;
                }
                third = second;
                second = nums[i];
                if (secondChange >= 1) {
                    thirdChange++;
                    secondChange++;
                } else if (secondChange == 0) {
                    secondChange++;
                }
            } else if (nums[i] >= third) {
                third = nums[i];
                thirdChange++;
            }
        }
        System.out.println(firstChange + " " + secondChange + " " + thirdChange);
        if (firstChange + secondChange + thirdChange >= 3) {
            return third;
        }
        return first;
    }
}
